package com.more.offer.algorithm.sort.sort_06;

/**
 * Date: 2020-03-15 23:35
 * Author: pinoc
 * Desc:
 */
public class QuickSort {
	public static void quickSort(int[] array, int low, int high) {
		//int[] array = {8,5,2,6,1,10,50,0,7,9,12};
		int basicIndex = low;
		int highIndex = high;
		if (high - low < 1) {
			return;
		}
		int basicValue = array[low]; //基数
		while (low < high) {
			//先移动高位
			while (basicValue <= array[high] && low < high) {
				high--;
			}
			while (basicValue >= array[low] && low < high) {
				low++;
			}
			//交换位置
			if (low < high) {
				int temp = array[low];
				array[low] = array[high];
				array[high] = temp;
			}
		}

		array[basicIndex] = array[low];
		array[low] = basicValue;

		quickSort(array, basicIndex, low - 1);
		quickSort(array, low + 1, highIndex);
	}

	public static void main(String[] args) {
		int[] array = {8,5,2,6,1,10,50,0,7,9,12,60,22,3};
		quickSort(array, 0 , array.length-1);
		for (int s : array) {
			System.out.print(s+" ");
		}
	}
}
